// 1. 使用除法：先计算非零元素的总乘积，根据 0 的个数分类处理每个位置的结果。

// step 1# 主函数：返回一个新数组，result[i] 为除 nums[i] 外所有元素的乘积
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int zeroCount = 0;       // 记录 0 的个数
    int totalPro = 1;        // 非 0 元素的乘积

    // step 2# 遍历数组，统计 0 的个数并计算非 0 元素的乘积
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 0) zeroCount++;         // 遇到 0 就计数
        else totalPro *= nums[i];              // 乘积不包括 0
    }

    // step 3# 如果数组中有两个或两个以上的 0，结果全为 0
    if (zeroCount >= 2) {
        for (int i = 0; i < numsSize; i++) {
            nums[i] = 0;  // 所有位置都为 0
        }
    }
    // step 4# 如果数组中恰好有一个 0，只有该位置为乘积，其余为 0
    else if (zeroCount == 1) {
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] == 0) nums[i] = totalPro;  // 0 的位置为乘积
            else nums[i] = 0;                      // 其他位置为 0
        }
    }
    // step 5# 如果没有 0，正常计算除当前元素外的乘积
    else {
        for (int i = 0; i < numsSize; i++) {
            nums[i] = totalPro / nums[i];  // 用总乘积除以当前元素
        }
    }

    // step 6# 设置返回数组的长度
    *returnSize = numsSize;
    return nums;  // 直接返回原数组作为结果（注意：LeetCode 可接受此写法）
}


// 2. 分别计算每个位置左侧和右侧所有数的乘积，最后相乘即为结果。

// step 1# 主函数：返回除自身以外的乘积数组
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    // step 2# 构建前缀积数组 pre，pre[i] 表示 nums[0..i-1] 的乘积
    int* pre = malloc(numsSize * sizeof(int));  // 分配前缀数组
    pre[0] = 1;  // 第一个元素左侧没有数，设为 1
    for (int i = 1; i < numsSize; i++) {
        pre[i] = pre[i - 1] * nums[i - 1];  // pre[i] = pre[i-1] * nums[i-1]
    }

    // step 3# 构建后缀积数组 suf，suf[i] 表示 nums[i+1..n-1] 的乘积
    int* suf = malloc(numsSize * sizeof(int));  // 分配后缀数组
    suf[numsSize - 1] = 1;  // 最后一个元素右侧没有数，设为 1
    for (int i = numsSize - 2; i >= 0; i--) {
        suf[i] = suf[i + 1] * nums[i + 1];  // suf[i] = suf[i+1] * nums[i+1]
    }

    // step 4# 构建最终结果数组 ans，每个位置为 pre[i] * suf[i]
    int* ans = malloc(numsSize * sizeof(int));  // 分配结果数组
    *returnSize = numsSize;  // 设置返回长度
    for (int i = 0; i < numsSize; i++) {
        ans[i] = pre[i] * suf[i];  // 除自身外的乘积 = 左乘积 × 右乘积
    }

    // step 5# 释放临时的前缀与后缀数组
    free(pre);
    free(suf);

    return ans;  // 返回结果数组
}

